#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-04 9:35 上午
# @Author  : yangdy
# @File    : 2020-08-04.207.课程表
# @Software: PyCharmCE
from my_methods import *


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        ans = True
        map = [[] for i in range(numCourses)]
        for p in prerequisites:
            map[p[0]].append(p[1])

        color = [0 for i in range(numCourses)]

        def dfs(node):
            if color[node] == 1:
                return False
            color[node] = 1
            for x in map[node]:
                if color[x] == 2:
                    continue
                if not dfs(x):
                    return False
            color[node] = 2
            return True

        for i in range(numCourses):
            if color[i] == 2:
                continue
            if not dfs(i):
                ans = False
                break

        return ans


questions = [
    (2, [[1, 0]],),
    (2, [[1, 0], [0, 1]],),
    (3, [[0, 1], [0, 2], [1, 2]],),
    (8, [[1, 0], [2, 6], [1, 7], [6, 4], [7, 0], [0, 5]]),
]

work(questions, lambda q: Solution().canFinish(q[0], q[1]))
